import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 33013
 * Date: 2023-04-13
 * Time: 22:25
 */

class MyCircularQueue {

    private int[] arr;
    private int front;
    private int real;

    public MyCircularQueue(int k) {
        arr = new int[k + 1];
    }

    public boolean enQueue(int value) {
        if ((real + 1) % arr.length == front){
            return false;
        }
        arr[real] = value;
        real = (real + 1) % arr.length;
        return true;
    }

    public boolean deQueue() {
        if (front == real){
            return false;
        }
        front = (front + 1) % arr.length;
        return true;
    }

    public int Front() {
        if (real == front){
            return -1;
        }
        return arr[front];
    }

    public int Rear() {
        if (front == real){
            return -1;
        }
        return arr[real - 1];
    }

    public boolean isEmpty() {
        if (front == real){
            return true;
        }
        return false;
    }

    public boolean isFull() {
        return (real + 1) % arr.length == front;
    }
}

class MyQueue {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        int size = stack1.size();
        for (int i = 0; i < size - 1; i++) {
            stack2.push(stack1.pop());
        }
        int x = stack1.pop();
        size = stack2.size();
        for (int i = 0; i < size; i++) {
            stack1.push(stack2.pop());
        }
        return x;
    }

    public int peek() {
        int size = stack1.size();
        for (int i = 0; i < size - 1; i++) {
            stack2.push(stack1.pop());
        }
        int x = stack1.peek();
        size = stack2.size();
        for (int i = 0; i < size; i++) {
            stack1.push(stack2.pop());
        }
        return x;
    }

    public boolean empty() {
        return stack1.empty();
    }
}

class MyStack {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if (queue1.isEmpty() && queue2.isEmpty()){
            queue1.offer(x);
            return;
        }
        if (queue1.isEmpty()){
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
    }

    public int pop() {
        if (queue2.isEmpty()){
            int size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                int n = queue1.poll();
                queue2.offer(n);
            }
            //int x = queue1.poll();
            return x;
        }
        int size = queue2.size();
        for (int i = 0; i < size - 1; i++) {
            int n = queue2.poll();
            queue1.offer(n);
        }
        return queue2.poll();
    }

    public int top() {
        int n = 0;
        if (queue2.isEmpty()){
            int size = queue1.size();
            for (int i = 0; i < size; i++) {
                n = queue1.poll();
                queue2.offer(n);
            }
            return n;
        }
        int size = queue2.size();
        for (int i = 0; i < size ; i++) {
            n = queue2.poll();
            queue1.offer(n);
        }
        return n;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }

}

public class MinStack {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MinStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int val) {
        if (stack1.empty() && stack2.empty()){
            stack1.push(val);
            stack2.push(val);
        }else {
            stack1.push(val);
            if (stack2.peek() >= val){
                stack2.push(val);
            }
        }
    }

    public void pop() {
        if (stack1.empty()){
            return;
        }
        int x = stack1.pop();
        if (x == stack2.peek()){
            stack2.pop();
        }
    }

    public int top() {
        return stack1.peek();
    }

    public int getMin() {
        return stack2.peek();
    }

    public static void main(String[] args) {

    }
}
